#ifndef SORT_H
#define SORT_H

/**
 * Standard heapsort.
 * build a binary heap of N elements,and perform N-1 deleteMaxes by swapping the last element in the heap with the first.When the algorithm terminates, the array contains the elements in sorted order.
 */
template <typename Comparable>
void heapsort( vector<Comparable> & a )
{
    for( int i = a.size( ) / 2 - 1; i >= 0; --i )  /* buildHeap */
        percDown( a, i, a.size( ) );
    for( int j = a.size( ) - 1; j > 0; --j )
    {
        std::swap( a[ 0 ], a[ j ] );               /* deleteMax */
        percDown( a, 0, j );                       /*交换后重新建堆,保证二叉堆的性质(父节点的键值大于等于任何一个子节点)*/
    }
}

/**
 * Internal method for heapsort.
 * inline函数避免了频繁调用函数对栈內重复开辟所带来的消耗
 * i is the index of an item in the heap.
 * Returns the index of the left child.
 */
inline int leftChild( int i )
{
    return 2 * i + 1;
}

/**
 * Internal method for heapsort that is used in
 * deleteMax and buildHeap.
 * i is the position from which to percolate down.
 * n is the logical size of the binary heap.
 */
template <typename Comparable>
void percDown( vector<Comparable> & a, int i, int n )
{
    int child;
    Comparable tmp;

    for( tmp = std::move( a[ i ] ); leftChild( i ) < n; i = child )
    {
        child = leftChild( i );
        if( child != n - 1 && a[ child ] < a[ child + 1 ] )
            //returns the index of the right child
	    ++child;
        if( tmp < a[ child ] )
	    //如果该节点比它的的右节点小,将右节点的数值复制到当前节点,即将较小的节点往下传以始终保证最大数在根节点
            a[ i ] = std::move( a[ child ] );
        else
            break;
    }
    //在空出来的节点存放移动后的键值
    a[ i ] = std::move( tmp );
}

/**
 * Mergesort:merge two sorted lists by recursive algorithm.
 * Internal method that makes recursive calls.
 * a is an array of Comparable items.
 * tmpArray is an array to place the merged result.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void mergeSort( vector<Comparable> & a,
                vector<Comparable> & tmpArray, int left, int right )
{   //递归结束:只剩一个元素
    if( left < right )
    {
        int center = ( left + right ) / 2;
	//分别处理左半边和右半边数组
        mergeSort( a, tmpArray, left, center );
        mergeSort( a, tmpArray, center + 1, right );
	//对已排好序的两部分排序后合并
        merge( a, tmpArray, left, center + 1, right );
    }
}

/**
 * Mergesort algorithm (driver).
 */
template <typename Comparable>
void mergeSort( vector<Comparable> & a )
{
    vector<Comparable> tmpArray( a.size( ) );

    mergeSort( a, tmpArray, 0, a.size( ) - 1 );
}


/**
 * Internal method that merges two sorted halves of a subarray.
 * a is an array of Comparable items.
 * tmpArray is an array to place the merged result.
 * leftPos is the left-most index of the subarray.
 * rightPos is the index of the start of the second half.
 * rightEnd is the right-most index of the subarray.
 */
template <typename Comparable>
void merge( vector<Comparable> & a, vector<Comparable> & tmpArray,
            int leftPos, int rightPos, int rightEnd )
{
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    // Main loop
    // 通过遍历数组中各元素,每一次比较将较小的元素放入数组实现排序
    while( leftPos <= leftEnd && rightPos <= rightEnd )
        if( a[ leftPos ] <= a[ rightPos ] )
            tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );
        else
            tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );

    while( leftPos <= leftEnd )    // 如果数组还有剩余不需要比较和遍历,直接Copy rest of first half
        tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );

    while( rightPos <= rightEnd )  // Copy rest of right half
        tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );

    // Copy tmpArray back
    for( int i = 0; i < numElements; ++i, --rightEnd )
        a[ rightEnd ] = std::move( tmpArray[ rightEnd ] );
}

/**
 * Simple recursive sorting algorithm
 * items:the array to be sorted
 */
template <typename Comparable>
void SORT( vector<Comparable> & items )
{
	if(items.size() > 1 )
	{
		vector<Comparable> smaller;
		vector<Comparable> same;
		vector<Comparable> larger;

		auto chosenItem = items[ items.size() / 2 ];
		
		//以vector中间位置的数为基准,将原vector拆分为三部分:smaller, larger, same
		//通过递归不断拆分实现排序
		for( auto & i : items )
		{
			if( i < chosenItem )
				smaller.push_back( std::move( i ));
			else if( chosenItem < i )
				larger.push_back( std::move(i));
			else
				same.push_back( std::move(i));}
		SORT( smaller );	//Recursive call!
		SORT( larger );		//Recursive call!
		//对排序好的vector进行组合
		std::move( begin( smaller ), end( smaller ), begin( items ));
		std::move( begin( same ), begin( items ) + smaller.size());
		std::move( begin( larger ), end( items ) - larger.size());
	}
}

/**
 * quicksort的一种选择pivot的方法
 * pivot选择的最佳策略:中位数
 * 实际操作:随机选择三个数取中间值
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a, int left, int right )
{

    int center = ( left + right ) / 2;
    //实现a[right] > a[center] > a[left]
    if( a[ center ] < a[ left ] )
        std::swap( a[ left ], a[ center ] );
    if( a[ right ] < a[ left ] )
        std::swap( a[ left ], a[ right ] );
    if( a[ right ] < a[ center ] )
        std::swap( a[ center ], a[ right ] );

        // Place pivot at position right - 1
    std::swap( a[ center ], a[ right - 1 ] );
    return a[ right - 1 ];
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right )
{
    //vector长度大于10时使用quicksort效率更高
    if( left + 10 <= right )
    {
        const Comparable & pivot = median3( a, left, right );

            // Begin partitioning
        int i = left, j = right - 1;
        for( ; ; )
        {
	    //向后移动i至a[i]>=pivot,向前移动j至a[j]<=pivot,通过交换使大于pivot的元素位于vector的后半部分,实现以pivot为基准分割vector
            while( a[ ++i ] < pivot ) { }
            while( pivot < a[ --j ] ) { }
            if( i < j )
                std::swap( a[ i ], a[ j ] );
            else
                break;
        }
	//i,j相遇后,此时index<i的元素小于pivot,>i的元素大于pivot,将pivot移到该位置后递归
        std::swap( a[ i ], a[ right - 1 ] );  // Restore pivot

        quicksort( a, left, i - 1 );     // Sort small elements
        quicksort( a, i + 1, right );    // Sort large elements
    }
    else  // Do an insertion sort on the subarray
	  // 长度小于10时,插入排序不需调用递归效率更高
        insertionSort( a, left, right );
}

#endif
